package com.wzq.solution;

import com.wzq.solution.node.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

class Solution101 {
    public static boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        Queue<TreeNode> left = new LinkedList<TreeNode>();
        Queue<TreeNode> right = new LinkedList<TreeNode>();
        
        if(root.left != null){
            left.add(root.left);
        }
        if(root.right != null){
            right.add(root.right);
        }


        while(!left.isEmpty() || !right.isEmpty()){
            if(left.size() != right.size()){
                return false;
            }
            
            TreeNode tmpLeft = left.poll();
            TreeNode tmpRight = right.poll();
            if(tmpLeft==null && tmpRight==null){
                continue;
            }else if(tmpLeft==null || tmpRight==null){
                return false;
            }
            if(tmpLeft.val != tmpRight.val){
                return false;
            }

            left.add(tmpLeft.left);
            left.add(tmpLeft.right);
            right.add(tmpRight.right);
            right.add(tmpRight.left);

        }
        return true;
    }


    public static boolean isSymmetric2(TreeNode root) {
        return isSymmetric2_(root.left,root.right);

    }
    public static boolean isSymmetric2_(TreeNode left,TreeNode right) {
        if(left == null && right == null){
            return true;
        }else if(left == null || right == null){
            return false;
        }
        if(left.val == right.val){
            return isSymmetric2_(left.left,right.right)&&isSymmetric2_(left.right,right.left);
        }else{
            return false;
        }
    }
    public static void main(String[] args) {

        TreeNode tn1 = new TreeNode(1);
        TreeNode tn2 = new TreeNode(2);
        TreeNode tn3 = new TreeNode(2);
        tn1.left = tn2;
        tn1.right = tn3;
        TreeNode tn4 = new TreeNode(3);
        TreeNode tn5 = new TreeNode(4);
        tn2.left = null;
        tn2.right = tn4;
        TreeNode tn6 = new TreeNode(4);
        TreeNode tn7 = new TreeNode(3);
        tn3.left = null;
        tn3.right = tn7;
        isSymmetric(tn1);
    }
}